package com.base.binarytree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SubStructureTree {
    /**
     * 判断B树是否是A树的子结构
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A,TreeNode B){
        /**
         * 广度优先，加递归
         */
        if (B==null){
            return false;
        }
        TreeNode curA;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(A);
        while (!queue.isEmpty()){
            curA =queue.remove();
            if (isEquals(curA,B)){
                return true;
            }
            if (curA.left!=null){
                queue.add(curA.left);
            }
            if (curA.right!=null){
                queue.add(curA.right);
            }
        }
        return false;


    }

    public boolean isEquals(TreeNode A,TreeNode B){
        if (B==null){
            return true;
        }
        if (A==null||A.val!=B.val){
            return false;
        }
        return isEquals(A.left,B.left)&&isEquals(A.right,B.right);
    }

    public boolean isSubStructure1(TreeNode A,TreeNode B){
        /**
         * 前序遍历加递归
         */
        if (B==null||A==null){
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(A);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if (isEquals(cur,B)){
                return true;
            }
            if (cur.right!=null)
                stack.push(cur.right);
            if (cur.left!=null)
                stack.push(cur.left);
        }
        return false;


    }
    public boolean isSubStructure2(TreeNode A,TreeNode B){
        /**
         * 递归加递归
         */
        if (B==null||A==null)
            return false;
        return isEquals(A,B)||isSubStructure2(A.left,B)||isSubStructure2(A.right,B);
    }


}
